1. Technical Field
This application relates to the field of digital certificates, and more particularly to the field of verifying and validating digital certificates and other information.
2. Description of Related Art
Digital signatures provide an effective form of Internet authentication. Unlike traditional passwords and PINs, digital signatures authenticate transactions in a way that is universally verifiable. Thus, it is very difficult, if not impossible, to repudiate a transaction that has been digitally signed. Digital signatures are produced via a signing key, SK, and verified via a matching verification key, PK. A user U keeps his own SK secret so that only U can sign on U's behalf. Fortunately, key PK does not “betray” the matching key SK; that is, knowledge of PK does not provide any practical advantage in computing SK. Therefore, a user U may make his own PK as public as possible so that every one can verify U's signatures. For this reason PK may be called the public key.
Digital certificates are alphanumeric strings that enable digital signatures by providing a guarantee that a given key PK is indeed the public key of a user U. A Certification Authority (CA) generates and issues a certificate to a user, but often only after being assured of the user's identity. Thus, the certificate proves that the CA has verified the holder's identity, and possibly other attributes. Certificates expire after a specified amount of time, often one year in the case of public CAs.
In essence, a digital certificate C consists of a CA's digital signature securely binding together several quantities: SN, a serial number unique to the certificate, PK, the public key of the user, U, the user's name, D1, the issue date, D2, the expiration date, and additional data. In symbols:C=SIGCA(SN,PK,U,D1,D2, . . . )
It is useful to be able to determine the status of a digital certificate, including determining whether a particular certificate was validly issued and/or whether the certificate has been revoked prior to the expiration thereof. There are a number of techniques for determining the status of an individual digital certificate. For example, U.S. Pat. Nos. 5,666,416 and 5,717,758 describe techniques for providing individual certificate status. Other techniques for disseminating and ascertaining certificate status are also known, including Certificate Revocation Lists (CRL's), which are digitally-signed lists of revoked certificates and the Online Certificate Status Protocol (OCSP) which specifies a mechanism for querying about the status of a particular certificate.
CRL's work by having each CA periodically issue a properly dated and digitally signed list (the CRL) containing serial numbers of the revoked certificates. In some implementations, a CRL contains all revoked certificates of a given set of certificates. Thus, the digital certificate may be presented with an electronic transaction which is compared to the most recent CRL. If the given certificate is not expired but is on the list as having been revoked, then it is known from the CRL that the certificate is not valid and the certificate holder is no longer authorized to conduct the transaction enabled by the digital certificate. On the other hand, if the certificate does not appear in the CRL, then the certificate is deemed valid. Either way, the CRL may be archived with other records of each transaction, so as to be able to prove, in the future, the transaction's validity or, in the case of a revoked certificate, justify denial of service.
Assuming a revocation rate of ten percent, then, on average, one in ten digital certificates is revoked prior to the expiration thereof. According to such a revocation rate, a system having ten million certificates would generate a CRL containing one million serial numbers, which could make the CRL unwieldy. Though this problem can be lessened by more recently introduced CRL-partition techniques, the basic strategy of bundling together the revocation information of many certificates is still likely to generate inconvenience and cost. If serial numbers are twenty four bits long (to handle a few million certificates) a sub-CRL of one thousand certificates would still be twenty four thousand bits (three thousand bytes) long. In some deployments, a CRL entry for each certificate, with overhead, may be as large as twenty-two bytes, thus making a one thousand certificate sub-CRL twenty-two thousand bytes long. This may be unacceptable in certain situations such as, for example, a wireless transaction, where having to transmit this many bits (as protection against future disputes and potential legal claims) may be impractical.
CRL's may grow big because they provide proofs of revocation (and thus, indirectly, of validity) about many certificates lumped together. By contrast, OCSP may provide for proofs of validity of individual certificates. Conventional OCSP services use OCSP responders that may receive a question from a client (i.e., a relying party) about the validity of a given certificate issued by a given CA, and, in response thereto, may provide a digitally signed answer indicating both the status of the certificate and time information about the answer.
To be able to provide OCSP services, a conventional OCSP responder is provided with information about the status of all of a CA's certificates. Since often it is up to the CA to decide the status of its own certificates, then, if the OCSP responder is the CA itself, the OCSP responder/CA already has the information about the revocation status of the certificates. If, on the other hand, the OCSP responder is not the CA, the OCSP responder may be kept updated about the status of the CA's certificates. See, for example, U.S. Pat. No. 5,717,758, Witness-Based Certificate Revocation System.
The CA may update an OCSP responder by sending a most recent CRL. The OCSP responder may consult the CRL to deduce whether a particular certificate of interest is currently valid or revoked so that the OCSP responder may provide a signed response to a relying party indicating the time of the current CRL, the time of the next update, and the time of actual processing.
Of course, a malicious/compromised OCSP responder may provide arbitrary signed answers about the certificates of a given CA, with or without consulting any CRL's. Accordingly, for the relying party to securely rely on the digitally signed answer of an OCSP responder about the certificates of a given CA, the OCSP includes a mechanism where the CA provides the OCSP responder with a responder certificate, a special digital certificate—signed by the CA—that essentially vouches to other parties that the CA trusts the OCSP responder to provide accurate proofs about the CA's certificates. Note that for this process to work appropriately, each OCSP responder (as well as every CA) must have a secret signing key, and this key must be protected (e.g., by placing the server implementing the responder in a vault).
Referring to FIG. 1, a diagram 40 illustrates a flow of information in a traditional OCSP environment. The diagram 40 includes a CA 42, a conventional OCSP responder 44, and a relying party 46. The bold lines used for the CA 42 and the OCSP responder 44 indicate the presence of a secret key that must be protected for the system to work reliably. The CA 42 provides validity information 48 (e.g., a CRL) to the OCSP responder 44. The relying party 46 provides an OCSP request 52 to the OCSP responder 44. The OCSP responder 44 examines the validity information provided by the CA 42 (e.g., in the form of a CRL) and to determine the validity status of the certificate in question. The OCSP responder 44 then prepares a corresponding response, digitally signs the response and provides the result thereof as an OCSP response 54 to the relying party 46. In some cases, the OCSP responder 44 may also provide a responder certificate 56 to the relying party 46 indicating that the OCSP responder 44 is empowered and entrusted by the CA 42.
There are significant drawbacks to OCSP. In the first place, digital signatures are computationally intensive operations. The digital signature created by a conventional OCSP responder on each OCSP response is generated at the time of the request, and may be the most computationally intensive part of the validation operation. For example, generating a digital signature may add between fifty milliseconds and one second to transaction time. Even if a conventional OCSP responder caches a digital signature about a digital certificate C after being asked the first time about C and then sent the cached signature when asked about C afterwards, still the answer to the first user asking about C may be significantly delayed due to generation of the initial digital signature.
In addition, if there is a single OCSP responder, then all certificate-validity queries would, eventually, be routed to the single OCSP responder, which then may become a major network bottleneck and cause considerable congestion and delays. If huge numbers of honest users suddenly queried this OCSP responder, then a disrupting denial of service situation could ensue.
On the other hand, to prevent the bottleneck problems of centralized implementations of OCSP, an organization may consider distributing the request load (about the validity of its certificates) across several, properly certified, conventional OCSP responders. In general, distributing the load of a single server across several (e.g., one hundred) servers, strategically located around the world (to avoid transmission bottlenecks), could alleviate network congestion. However, for OCSP, load distribution may introduce additional problems because, in order to provide signed responses to the certificate-validity queries, each of the one hundred distributed conventional OCSP responders would have its own secret signing key. Thus, compromising any of the one hundred servers could effectively compromise the entire organization. Indeed, if a conventional OCSP responder were compromised, an attacker could use the discovered secret signing key to sign responses falsely indicating that (1) valid certificates are revoked, or (2) revoked certificates are still valid. This latter type of false-positive response could, for example, allow a terminated employee to regain access to systems.
One way to prevent a responder from being compromised is to run the responder from a secure vault, with 24×7 surveillance. Unfortunately, this is a costly option. A truly secure vault, meeting all the requirements of—say—a financial CA, may cost over one million dollars to build and one million dollars a year to operate. In addition, even if an organization were willing to pick up such expenses, vaults can not be built overnight. Thus if a CA needed a few more vaults to lessen the load of its current conventional OCSP responders, there may be a delay of months before new properly-vaulted OCSP responders could be constructed.
Moreover, incurring the costs of multiple vaults may not solve the OCSP security problems. This is because the OCSP mechanism requires that a conventional OCSP responder receive requests coming from un-trusted sources (the relying parties) and then service the requests using the secret signing key of the responder. A malicious relying party (or a malicious agent posing as a relying party) might thus prefer exposing the OCSP responder signing key by exploiting a possible weakness in the underlying operating system.
Furthermore, there are difficulties associated with OCSP with respect to servicing certificate validity requests originating from different security domains. For instance, conventional OCSP responders run by organization A may easily provide responses about the status of certificates of the CA of organization A, but OCSP responders run by another organization may not have enough information to provide responses about “foreign” certificates.
This problem, deriving from lack of specific knowledge, could be addressed in one of two ways. First, the relying parties from organization B could obtain from the responders from organization A the status of certificates from the CA of organization A. This limits performance however, since the OCSP responders from organization A may be geographically distant from relying parties of organization B, so network times may greatly slow overall validation processing. A second alternative is to allow responders from organization B to make responses about certificates from organization A, by having the CA from organization A forward CRLs from organization A to foreign responders. Indeed, CRLs are digitally signed and thus need not be kept secret, and the CA from organization A presumably wishes to inform the largest possible audience about the validity status of certificates from organization A. This second alternative provides an OCSP responder of organization B sufficient information for answering a request from a relying party about a certificate of organization A. But for the relying party to take seriously the digitally signed answer of an OCSP responder of organization B, the CA from organization A should also certify the foreign responder as trustworthy for answering validity queries about certificates from organization A.
Referring to FIG. 2, a diagram 60 illustrates the CA 42, the conventional OCSP responder 44, and the relying party 46 shown in the diagram 40 of FIG. 1. However, in the situation illustrated by the diagram 60, the relying party 46 provides an OCSP request 62 about a certificate that is not managed by the CA 42 but, instead, was issued and is managed by a different CA 64. In such a case, the OCSP responder 44 may not provide an OCSP response based solely on information within the CRL 48 provided by the CA 42 to the OCSP responder 44. Instead, the CA 64 provides a different CRL 66 and a different responder certificate 68 to the OCSP responder 44. The OCSP responder 44 may then use the different CRL 66 to formulate an OCSP response 72 about the foreign certificate. In some cases, the OCSP responder 44 may also provide to the relying party 46 the responder certificate 68.
This second alternative may provide better scalability and performance, but it muddies the security and trust flow between the two organizations. In the diagram 60, the OCSP responder 44 is making an authoritative response to the relying party that a certificate of the CA 64 is still good. If the OCSP responder 44 makes an incorrect response for any reason (misconfiguration, hostile attack, or straightforward dishonesty), the OCSP responder 44 may thus negatively impact the organization of the CA 64. By allowing the OCSP responder 44 to make authoritative claims about certificates of the organization of the CA 64, the organization of the CA 64 is relinquishing some of the trust that it previously held.
As an example, consider the case where the organizations are credit card issuers. A bank from organization A revokes the certificate for a user, and the bank pays to ensure that conventional OCSP responders from organization A are secure and reliable. Assume that the OCSP responders from organization B are misconfigured, so when a merchant relying party from organization B asks about the validity of the user, the responders of organization B incorrectly respond that the user is valid. The merchant accepts this answer and allows a transaction to proceed for the revoked user. This type of delegation-of-trust between organizations may be acceptable in some cases, but it is not a generally useful alternative for any large-scale heterogeneous deployment of traditional OCSP.
It is desirable to provide a system that addresses the difficulties discussed above.